package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;


/**
 * 分析：
 * 
 * 实现：
 * 
 * 经验和教训：
 * 
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1035 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1035.class.getResource("P1035.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		Map<String, Integer> maps = new HashMap<String, Integer>();
		int count = 0;
		String line = stdin.readLine();
		while (line != null && !"#".equals(line)) {
			String word = line.trim(); 
			maps.put(word, count++);
			line = stdin.readLine();
		}
		
		line = stdin.readLine();
		while (line != null && !"#".equals(line)) {
			String word = line.trim();
			check(word, maps);
			line = stdin.readLine();
		}
	}
	
	private static void check(String word, final Map<String, Integer> maps) {
		
		if (maps.get(word) != null) {
			System.out.println(word + " is correct");
		} else {
			Set<String> set = new HashSet<String>();
			//delete a letter
			for (int i = 0; i < word.length(); i ++) {
				String nw = word.substring(0, i) + word.substring(i+1);
				if (maps.get(nw) != null) {
					set.add(nw);
				}
			}
			//replace a letter
			for (int i = 0; i < word.length(); i ++) {
				String n1 = word.substring(0, i);
				String n2 = word.substring(i+1);
				for (int c = 'a'; c <= 'z'; c ++) {
					String nw = n1 + ((char)c) + n2;
					if (maps.get(nw) != null) {
						set.add(nw);
					}
				}
			}
			//insert a letter
			for (int i = 0; i < word.length()+1; i ++) {
				String n1 = word.substring(0, i);
				String n2 = word.substring(i);
				for (int c = 'a'; c <= 'z'; c ++) {
					String nw = n1 + ((char)c) + n2;
					if (maps.get(nw) != null) {
						set.add(nw);
					}
				}
			}
			
			String[] array = set.toArray(new String[set.size()]);
			Arrays.sort(array, new Comparator<String>() {

				public int compare(String w1, String w2) {
					return maps.get(w1).compareTo(maps.get(w2));
				}
				
			});
			
			//result
			String str = word + ":";
			for (int i = 0; i < array.length; i ++) {
				str += " " + array[i];
			}
			System.out.println(str);
		}
	}
	
}